#include<iostream>
#include<vector>
#include<string>
using namespace std;

//784.字母大小写全排列
//全局变量
vector<string> ret1;
string path1;
void dfs1(string s,int i){
    //结束条件
    if(i==s.size()){
        ret1.push_back(path1);
        return;
    }

    //剪枝,判断当前元素是数字还是字母
    if(s[i]>='0'&&s[i]<='9'){
        path1 += s[i];
        dfs1(s, i + 1);
        //回溯
        path1.pop_back();
    }
    else{
        //选择大写字母
        path1 += toupper(s[i]);
        dfs1(s, i + 1);
        //回溯
        path1.pop_back();

        //选择小写字母
        path1 += tolower(s[i]);
        dfs1(s, i + 1);
        //回溯
        path1.pop_back();
    }
}
vector<string> letterCasePermutation(string s){
    dfs1(s, 0);
    return ret1;
}

//526.优美的排列
//全局变量
int ret2 = 0;
vector<bool> check;
vector<int> perm;
void dfs2(int n,int pos){
    //结束条件，注意这里要大于n时才结束，不是等于n
    if(pos>n){
        ret2++;
        return;
    }

    for (int i = 1; i <= n;i++){
        //剪枝，已经使用过的数字不能再次使用
        //并且当前下标可以整除当前数字或者当前数字可以整除下标
        if(check[i]==false&&(pos%i==0||i%pos==0)){
            perm[pos] = i;
            check[i] = true;

            dfs2(n, pos + 1);
            //回溯操作时，perm不能直接删去最后一个，可以前当前位置置为0
            perm[pos] = 0;
            check[i] = false;
        }
    }
}

int countArrangement(int n){
    perm.resize(n+1);
    check.resize(n + 1);
    dfs2(n, 1);
    return ret2;
}

//51.N皇后
vector<vector<string>> ret3;
vector<string> path3;
//列数组
vector<bool> checkcol;
//主对角线数组
vector<bool> checkdig1;
//副对角线数组
vector<bool> checkdig2;
void dfs3(int n,int i){
    //i表示行数，j表示列数
    //递归实现行数循环，函数内用for实现列数循环
    //结束条件
    if(i==n){
        ret3.push_back(path3);
        return;
    }

    for (int j = 0; j < n;j++){
        //剪枝
        if(checkcol[j]==false&&checkdig1[j-i+n]==false&&checkdig2[j+i]==false){
            path3[i][j] = 'Q';
            checkcol[j] = checkdig1[j - i + n] = checkdig2[j + i] = true;

            dfs3(n, i + 1);
            //回溯
            path3[i][j] = '.';
            checkcol[j] = checkdig1[j - i + n] = checkdig2[j + i] = false;
        }
    }
}
vector<vector<string>> solveNQueens(int n){
    checkcol.resize(n);
    //对角线的两个数组空间大小是2n
    checkdig1.resize(2 * n);
    //刚开始这个数组空间大小设置成了n，导致找了一个小时错
    checkdig2.resize(2 * n);
    path3.resize(n);
    for (int i = 0;i<n;i++){
        path3[i].append(n, '.');
    }
    dfs3(n, 0);
    return ret3;
}


//36.有效的数独
//行数组和列数组用来判断当前行或者列是否存在该数字
//例如checkrow[2][7]表示第三行是否存在7这个数
bool checkrow[9][10];
bool checkcol[9][10];
//grid数组用来将整个9*9数组分成小的3*3表示
//grid[2][2][6]表示第三行第三列是否存在6这个数
bool grid[3][3][10];
bool isValidSudoku(vector<vector<char>>& board){
    for (int i = 0; i < board.size();i++){
        for (int j = 0; j < board[i].size();j++){
            if(board[i][j]!='.'){
                int num = board[i][j] - '0';
                if(checkrow[i][num]||checkcol[j][num]||grid[i/3][j/3][num]){
                    return false;
                }
                checkrow[i][num] = checkcol[j][num] = grid[i / 3][j / 3][num] = true;
            }
        }
    }

    return true;
}


//37.解数独
//重点是返回，当返回true时，表示找到正确结果，不再继续递归
bool dfs(vector<vector<char>>& board){
    //两层循环，先循环列再循环行
    for (int i = 0; i < board.size();i++){
        for (int j = 0; j < board[i].size();j++){
            if(board[i][j]=='.'){
                //空位置填入数字1到9循环
                for (int num = 1; num <= 9;num++){
                    if(checkrow[i][num]==false&&checkcol[j][num]==false&&grid[i/3][j/3][num]==false){
                        board[i][j] = num + '0';
                        checkrow[i][num] = checkcol[j][num] = grid[i / 3][j / 3][num] = true;
                        //找到正确结果就返回，不再递归
                        if(dfs(board)==true){
                            return true;
                        }

                        //回溯
                        board[i][j] = '.';
                        checkrow[i][num] = checkcol[j][num] = grid[i / 3][j / 3][num] = false;
                    }
                }
                //当1到9都填完时，还没有返回true,说明当前的排列错误
                return false;
            }
        }
    }
    // 当外层行数循环结束表示找到正确的结果，一直向上返回true
    return true;
}
void solveSudoku(vector<vector<char>>& board){
    //先将当前已有的数字在三个数组中标记
    for (int i = 0;i<board.size();i++){
        for (int j = 0;j<board[i].size();j++){
            if(board[i][j]!='.'){
                int num = board[i][j] - '0';
                checkrow[i][num] = checkcol[j][num] = grid[i / 3][j / 3][num] = true;
            }
        }
    }
    dfs(board);
}

int main(){
    vector<vector<string>> ans=solveNQueens(6);
    for(auto numi : ans){
        for(auto numj : numi){
            for(auto ch : numj){
                cout << ch << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}